Jackson bắt đầu thực hiện những chất liệu mới cho album vào tháng 10 năm 1997, và kết thúc với việc thu âm "You Are My Life" chỉ 8 tuần trước ngày nó ra lò, trở thành album tốn kém thời gian nhất trong sự nghiệp của Jackson.[7] Những bài hát hợp tác với Rodney Jerkins được thu âm tại The Hit Factory ở Miami, Florida.[8] Jackson mong muốn có sự tham gia của ít nhất một rapper trong một bài hát, và phải là "rapper nổi tiếng".[2] Phát ngôn viên của Jackson đề nghị raper Fats đến từ New Jersey; sau khi Jackson nghe bản hoàn thiện của các bài hát, cả hai đồng ý thu âm cùng nhau một bài hát khác cho album.[2] Rodney Jerkins nói rằng Jackson đang tìm tòi một định hướng âm nhạc mới so với trước.[2] Jackson đóng vai trò sáng tác và sản xuất ở phần lớn các bài hát trong Invincible. Ngoài Jackson, album còn có sự góp sức từ Teddy Riley, Andre Harris, Andraeo "Fanatic" Heard, Kenneth "Babyface" Edmonds, R. Kelly và Dr. Freeze Bill Gray và hỗ trợ viết lời từ Kelly, Fred Jerkins III, LaShawn Daniels, Nora Payne và Robert Smith.[9] Album đánh dấu lần thứ 3 Jackson và Riley cộng tác cùng nhau, hai lần trước là trong Dangerous và Blood on the Dance Floor: HIStory in the Mix. Việc thực hiện Invincible tiêu tốn 30 triệu đô-la,[10] trở thành album đắt nhất từng được thực hiện.[11]